class Solution {
public:
    string robotWithString(string s) {

        string ret;
        stack<char> st;
        vector<char> f(s.size());
        f[s.size()-1]='z'+1;
        for(int i=s.size()-2;i>=0;i--){

            f[i]=min(s[i+1],f[i+1]);
        }
        for(int i=0;i<s.size();i++){

            st.push(s[i]);
            while(st.size() && f[i]>=st.top()){

                char c=st.top();
                st.pop();
                ret.push_back(c);
            }            
        }
        while(st.size()){

            char c=st.top();
            st.pop();
            ret.push_back(c);
        }        
        return ret;
    }
};
